|
|
Algebraic Substructures in Cm
Kala, Vítězslav ; Kepka, Tomáš (advisor) ; Stanovský, David (referee) ; El Bashir, Robert (referee)
Title: Algebraic Substructures in ℂ Author: Vítězslav Kala Department: Department of Algebra Supervisor: Prof. RNDr. Tomáš Kepka, DrSc., Department of Algebra Abstract: We study the structure of finitely generated semirings, parasemifields and other algebraic structures, developing and applying tools based on the geom- etry of algebraic substructures of the Euclidean space ℂ . To a parasemifield which is finitely generated as a semiring we attach a certain subsemigroup of the semigroup ℕ0 (defined using elements such that + = for some ∈ and ∈ ℕ). Algebraic and geometric properties of carry important structural information about ; we use them to show that if a parasemifield is 2-generated as a semiring, then it is additively idempotent. We also provide a ring-theoretic reformulation of this conjecture in the case of -generated semirings. We also classify all additively idempotent parasemifields which are finitely gen- erated as semirings by using the fact that they correspond to certain finitely generated unital lattice ordered groups. Busaniche, Cabrer, and Mundici [4] re- cently classified these using the combinatorial and geometric notion of a stellar sequence which is a sequences of certain simplicial complexes in [0, 1] . We use their results to prove that each such parasemifield is a finite product of...
|
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee)
In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...
|
|
|
Geometric and algebraic properties of discrete structures
Rytíř, Pavel ; Loebl, Martin (advisor) ; Serra, Oriol (referee) ; Kaiser, Tomáš (referee)
In the thesis we study two dimensional simplicial complexes and linear codes. We say that a linear code C over a field F is triangular representable if there exists a two dimensional simplicial complex ∆ such that C is a punctured code of the kernel ker ∆ of the incidence matrix of ∆ over F and dim C = dim ker ∆. We call this simplicial complex a geometric representation of C. We show that every linear code C over a primefield is triangular representable. In the case of finite primefields we construct a geometric representation such that the weight enumerator of C is obtained by a simple formula from the weight enumerator of the cycle space of ∆. Thus the geometric representation of C carries its weight enumerator. Our motivation comes from the theory of Pfaffian orientations of graphs which provides a polynomial algorithm for weight enumerator of the cut space of a graph of bounded genus. This algorithm uses geometric properties of an embedding of the graph into an orientable Riemann surface. Viewing the cut space of a graph as a linear code, the graph is thus a useful geometric representation of this linear code. We study embeddability of the geometric representations into Euclidean spaces. We show that every binary linear code has a geometric representation that can be embed- ded into R4 . We characterize...
|
|
|
Algebraic Substructures in Cm
Kala, Vítězslav ; Kepka, Tomáš (advisor) ; Stanovský, David (referee) ; El Bashir, Robert (referee)
Title: Algebraic Substructures in ℂ Author: Vítězslav Kala Department: Department of Algebra Supervisor: Prof. RNDr. Tomáš Kepka, DrSc., Department of Algebra Abstract: We study the structure of finitely generated semirings, parasemifields and other algebraic structures, developing and applying tools based on the geom- etry of algebraic substructures of the Euclidean space ℂ . To a parasemifield which is finitely generated as a semiring we attach a certain subsemigroup of the semigroup ℕ0 (defined using elements such that + = for some ∈ and ∈ ℕ). Algebraic and geometric properties of carry important structural information about ; we use them to show that if a parasemifield is 2-generated as a semiring, then it is additively idempotent. We also provide a ring-theoretic reformulation of this conjecture in the case of -generated semirings. We also classify all additively idempotent parasemifields which are finitely gen- erated as semirings by using the fact that they correspond to certain finitely generated unital lattice ordered groups. Busaniche, Cabrer, and Mundici [4] re- cently classified these using the combinatorial and geometric notion of a stellar sequence which is a sequences of certain simplicial complexes in [0, 1] . We use their results to prove that each such parasemifield is a finite product of...
|
|
|
Topological and geometrical combinatorics
Tancer, Martin ; Matoušek, Jiří (advisor) ; Pultr, Aleš (referee) ; Kaiser, Tomáš (referee) ; Meshulam, Roy (referee)
1 Topological and Geometrical Combinatorics Martin Tancer Abstract The task of the thesis is to present several new results on topological methods in combinatorics. The results can be split into two main streams. The first stream regards intersection patterns of convex sets. It is shown in the thesis that finite projective planes cannot be intersection patterns of convex sets of fixed dimension which answers a question of Alon, Kalai, Matoušek and Meshulam. Another result shows that d-collapsibility (a necessary condition on properties of in- tersection patterns of convex sets in dimension d) is NP-complete for recognition if d ≥ 4. In addition it is shown that d-collapsibility is not a necessary condition on properties of intersection patterns of good covers, which disproves a conjecture of G. Wegner from 1975. The second stream considers algorithmic hardness of recognition of simplicial com- plexes embeddable into Rd . The following results are proved: It is algorithmically un- decidable whether a k-dimensional simplicial complex piecewise-linearly embeds into Rd for d ≥ 5 and k ∈ {d−1, d}; and this problem is NP-hard if d ≥ 4 and d ≥ k ≥ 2d−2 3 .
|
guest ::
